package history

import (
	"container/heap"
	"math"
)

/**
 * @Description: 剑指 Offer 63. 股票的最大利润
 * @Keyword: 买卖一次最大利润
 * @Author: kami
 * @Date: 2022/5/23 20:05
 **/
func maxProfit(prices []int) int {
	var cost = math.MaxInt
	var profit = 0
	for _, price := range prices {
		if cost > price {
			cost = price
		}
		if price-cost > profit {
			profit = price - cost
		}
	}
	return profit
}

/**
 * @Description: 2034. 股票价格波动
 * @Keyword:
 * @Author: kami
 * @Date: 2022/5/24 8:06
 **/
type StockPrice struct {
	maxPrice, minPrice hp
	timePriceMap       map[int]int
	maxTimestamp       int
}

func Constructor() StockPrice {
	return StockPrice{timePriceMap: map[int]int{}}
}

func (sp *StockPrice) Update(timestamp, price int) {
	heap.Push(&sp.maxPrice, pair{-price, timestamp})
	heap.Push(&sp.minPrice, pair{price, timestamp})
	sp.timePriceMap[timestamp] = price
	if timestamp > sp.maxTimestamp {
		sp.maxTimestamp = timestamp
	}
}

func (sp *StockPrice) Current() int {
	return sp.timePriceMap[sp.maxTimestamp]
}

func (sp *StockPrice) Maximum() int {
	for {
		if p := sp.maxPrice[0]; -p.price == sp.timePriceMap[p.timestamp] {
			return -p.price
		}
		heap.Pop(&sp.maxPrice)
	}
}

func (sp *StockPrice) Minimum() int {
	for {
		if p := sp.minPrice[0]; p.price == sp.timePriceMap[p.timestamp] {
			return p.price
		}
		heap.Pop(&sp.minPrice)
	}
}

type pair struct{ price, timestamp int }
type hp []pair

func (h hp) Len() int            { return len(h) }
func (h hp) Less(i, j int) bool  { return h[i].price < h[j].price }
func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

/**
 * @Description: 121. 买卖股票的最佳时机
 * @Keyword: 简单
 * @Author: kami
 * @Date: 2022/5/24 10:47
 **/
func maxProfitSimple(prices []int) int {
	var cost = prices[0]
	var profit = 0
	for i := 0; i < len(prices); i++ {
		if prices[i]-cost > profit {
			profit = prices[i] - cost
		}
		if cost > prices[i] {
			cost = prices[i]
		}
	}
	return profit
}

/**
 * @Description: 901. 股票价格跨度
 * @Keyword: 价格变化
 * @Author: kami
 * @Date: 2022/5/24 11:09
 **/
type StockSpanner struct {
	// 当天对应连续天数，当天的价格
	dp [][]int
}

func Constructor1() StockSpanner {
	return StockSpanner{
		dp: [][]int{{0, -1}},
	}
}

func (this *StockSpanner) Next(price int) int {
	var size = len(this.dp)
	if price < this.dp[size-1][1] {
		this.dp = append(this.dp, []int{1, price})
	} else {
		// 当天价格大于前一天的价格，需要回查找到大于当天价格的索引
		var preIdx = size - 1
		var cnt = 1
		for preIdx > 0 {
			if price < this.dp[preIdx][1] {
				break
			} else {
				cnt += this.dp[preIdx][0]
				preIdx -= this.dp[preIdx][0]
			}
		}
		this.dp = append(this.dp, []int{cnt, price})
	}
	return this.dp[len(this.dp)-1][0]
}

/**
 * @Description: 122. 买卖股票的最佳时机 II
 * @Keyword: 多次买卖
 * @Author: kami
 * @Date: 2022/5/24 12:55
 **/
func maxProfit122(prices []int) int {
	var profit = 0
	for i := 1; i < len(prices); i++ {
		var diff = prices[i] - prices[i-1]
		if diff > 0 {
			profit += diff
		}
	}
	return profit
}

/**
 * @Description: 123. 买卖股票的最佳时机 III
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/5/24 13:08
 **/
func maxProfit123(prices []int) int {
	buy1, sell1 := prices[0], 0
	buy2, sell2 := prices[0], 0
	for i := 1; i < len(prices); i++ {
		buy1 = min(buy1, prices[i])
		sell1 = max(sell1, prices[i]-buy1)

		buy2 = min(buy2, sell1-prices[i])
		sell2 = max(sell2, prices[i]-buy2)
	}
	return sell2
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func maxProfit123_v2(prices []int) int {
	var size = len(prices)
	var dp1 = make([]int, size)
	var dp2 = make([]int, size)

	var preMinVal = prices[0]
	var backMaxVal = prices[size-1]
	for i := 1; i < size; i++ {
		dp1[i] = max(dp1[i-1], prices[i]-preMinVal)
		preMinVal = min(preMinVal, prices[i])

		dp2[size-i-1] = max(dp2[size-i], backMaxVal-prices[size-i-1])
		backMaxVal = max(backMaxVal, prices[size-i-1])
	}
	var res int
	for i := 1; i < size; i++ {
		res = max(dp1[i-1]+dp2[i], res)
	}
	// 只买一次或者两次
	return max(dp1[size-1], res)
}

/**
 * @Description: 188. 买卖股票的最佳时机 IV
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/5/24 17:35
 **/
func maxProfit188(k int, prices []int) int {
	if len(prices) == 0 || k == 0 {
		return 0
	}

	dp := make([][]int, k)
	for i := 0; i < k; i++ {
		dp[i] = make([]int, 2) //dp[i][0]：第i次买最大收益；dp[i][1]：第i次卖最大收益
	}
	for i := 0; i < k; i++ {
		dp[i][0] = -prices[0]
		dp[i][1] = 0
	}

	n := len(prices)
	for i := 0; i < n; i++ {
		for j := 0; j < k; j++ {
			if j == 0 {
				dp[j][0] = max(dp[j][0], -prices[i])
				dp[j][1] = max(dp[j][1], dp[j][0]+prices[i])
			} else {
				dp[j][0] = max(dp[j][0], dp[j-1][1]-prices[i]) //非第一次买，则收益为前一次卖后收益-当前价格
				dp[j][1] = max(dp[j][1], dp[j][0]+prices[i])
			}
		}
	}

	return dp[k-1][1]
}

/**
 * @Description: 2110. 股票平滑下跌阶段的数目
 * @Keyword: 记录每个节点的连续数目
 * @Author: kami
 * @Date: 2022/5/25 9:18
 **/
func getDescentPeriods(prices []int) int64 {
	var preIdx = len(prices) - 1
	var cnt = 0
	for i := len(prices) - 2; i >= 0; i-- {
		if prices[i]-prices[i+1] != 1 {
			preIdx = i
		}
		cnt += preIdx - i
	}

	return int64(cnt + len(prices))
}

/**
 * @Description: 309. 最佳买卖股票时机含冷冻期
 * @Keyword: 动态对话
 * @Author: kami
 * @Date: 2022/5/25 10:17
 **/
func maxProfit309(prices []int) int {
	if len(prices) == 0 {
		return 0
	}
	n := len(prices)
	// f[i][0]: 手上持有股票的最大收益
	// f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
	// f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
	f := make([][3]int, n)
	f[0][0] = -prices[0]
	for i := 1; i < n; i++ {
		f[i][0] = max(f[i-1][0], f[i-1][2]-prices[i])
		f[i][1] = f[i-1][0] + prices[i]
		f[i][2] = max(f[i-1][1], f[i-1][2])
	}
	return max(f[n-1][1], f[n-1][2])
}

/**
 * @Description: 714. 买卖股票的最佳时机含手续费
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/5/25 10:33
 **/
func maxProfit714(prices []int, fee int) int {
	var dp = new([2]int)
	dp[1] = -prices[0]
	for i := 0; i < len(prices); i++ {
		var tmp = dp[0]
		dp[0] = max(dp[0], dp[1]+prices[i]-fee)
		dp[1] = max(dp[1], tmp-prices[i])
	}
	return dp[0]
}
